% Compiler avec pdflatex
% Pour convertir les .dia en eps => export dia
% Pour convertir les .eps en png => gimp
% => dia => png directement par dia : problemes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Répartition
% Mickael : développement (fct general, reception message, retransmission, messages manquants
% Bruno : specifications
% Pierre-Yves : interface
% Guillaume : démonstration 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass{beamer}
\definecolor{beamer@struct}{rgb}{0.07,0.2,0.33}
\definecolor{grey}{rgb}{0.9,0.9,0.9}
\setbeamercolor{structure}{fg=beamer@struct}


\mode<presentation>
{
  \usetheme{Malmoe}
 \setbeamertemplate{navigation symbols}{}
 \setbeamertemplate{blocks}[rounded][shadow=true]  % pour  les arrondis,
\setbeamercolor{block title}{fg=white,bg=beamer@struct}
\setbeamercolor{block body}{fg=black,bg=grey}
  \usecolortheme{default}
  \usefonttheme[onlysmall]{structurebold}
}

\usepackage{graphics}
\usepackage{graphicx}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{graphics}
\setbeamercovered{dynamic}

% Reaffiche le sommaire a chaque debut de Section
%\AtBeginSection[]
%{
%  \begin{frame}<beamer>
%    \frametitle{Sommaire}
%    \tableofcontents[current,currentsection,hideothersubsections]
%  \end{frame}
%}
% Reaffiche le sommaire a chaque debut de SubSection
%\AtBeginSubsection[]
%{
%  \begin{frame}<beamer>
%    \frametitle{Sommaire}
%    \tableofcontents[current,currentsubsection]
%  \end{frame}
%}

\title[Application de discussion dans un réseau dynamique]{SR05 - Application de discussion dans un réseau fortement dynamique} 
\author[SR05]{G.~Kania \and P.-Y.~Lozachmeur \and M.~Magniez \and B.~Sabos \and G.~Tremeau \and M.~Gaspard}
\institute{Université de Technologie de Compiègne}
\date{22 décembre 2006}
\subject{SR05 - Application de discussion dans un réseau fortement dynamique} 

\newcommand{\p}{\par \vspace{0.5cm}}


\pgfdeclareimage[height=0.5cm]{logo}{images/mouche}
\logo{ \pgfuseimage{logo} }


\begin{document}


\frame{\titlepage}


\part<presentation>{presentation}

\section{Introduction}
		\begin{frame}
			\frametitle{Introduction}
				\begin{block}{Projet SR05}
				 \begin{itemize}
					\item Application décentralisée de discussion entre des voitures
					\item Organisation en mode projet,  réunions hebdomadaires
					\item Outils pour la gestion des sources et des informations (SVN, Wiki)
					\item Développement d'un outil pour gérer la simulation de réseau
				\end{itemize}				
				\end{block}	
		\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Spécifications
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Spécifications}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Présentation du sujet
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\subsection{Présentation du projet}
		\begin{frame}
\begin{small}
			\frametitle{Présentation du projet}
 \begin{itemize}
      \item<1->{Messagerie instantanée}\\
      \item<1->{Discussion par salons publics}\\

      \item<2->{Possibilité de créer plusieurs salons}\\
	      \uncover<2->{$\hookrightarrow$ Le créateur en devient le centre}\\
	      \uncover<2->{$\hookrightarrow$ Salon d'une taille définie autour du centre}\\
\vspace{0.5cm}
      \item<3->{Possibilité de rejoindre un ou plusieurs salons}\\
	      \uncover<3->{$\hookrightarrow$ Ne voit que les salons dont les centres sont à portée}\\
\vspace{0.5cm}
      \item<4->{Mise à jour continue de l'environnement et de l'état des salons}\\
	      \uncover<4->{$\hookrightarrow$ Connaître ses voisins directs}\\
	      \uncover<4->{$\hookrightarrow$ Connaître l'état des participants aux salons}\\
	      \uncover<4->{$\hookrightarrow$ Suivre les connexions et déconnexions des participants}
 \end{itemize}
\end{small}
		\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Interface
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\subsection{Interface}
		\begin{frame}
			\frametitle{Interface}
\begin{center}
\includegraphics[width=2.5cm,clip]{network.png}\\
\includegraphics[width=9cm,clip]{A.png}
\end{center}
		\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Gestion des salons
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\subsection{Gestion des messages}
		\begin{frame}
			\frametitle{Gestion des messages}
\begin{small}
 \begin{itemize}
      \item<1->{Diffusion des messages}\\
	      \uncover<1->{\hspace{0.2cm}$\hookrightarrow$ Tous les noeuds du réseau participent à la propagation de l'ensemble des messages}\\
	      \uncover<1->{\hspace{0.2cm}$\hookrightarrow$ Dans la limite d'un salon ou dans la portée d'un centre}\\
	      \uncover<1->{\hspace{0.2cm}$\hookrightarrow$ Utilisation minimale du réseau lors des propagations par préselection des destinataires et anticipation de réception}\\
\vspace{0.2cm}
      \item<2->{Mise à jour de l'état des clients distants}\\
	      \uncover<2->{\hspace{0.2cm}$\hookrightarrow$ Choix de l'horloge vectorielle}\\
	      \uncover<2->{\hspace{0.2cm}$\hookrightarrow$ Demande groupée de réémission en vague mourante}\\
\vspace{0.2cm}
      \item<3->{Ordonnancement des messages retransmis}\\
	      \uncover<3->{\hspace{0.2cm}$\hookrightarrow$ Choix des estampilles}\\
\vspace{0.2cm}
      \item<4->{Connaître ses voisins directs et leur distance par message "ping"}
 \end{itemize}
\end{small}
		\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Gestion des salons
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\subsection{Gestion des salons}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Taille maximale d'un salon
		\begin{frame}
			\frametitle{Gestion des salons}
\begin{small}
 \begin{itemize}
      \item Taille maximale d'un salon\\
\uncover<1-2>{$\times$ Position géographique par coordonnées GPS}\\
\uncover<1-2>{\hspace{0.8cm}$\hookrightarrow$ Présence et disponibilité continue d'un récepteur GPS.}\\
\uncover<1-2>{\hspace{0.8cm}$\hookrightarrow$ Inadéquation entre la topologie et l'homogénéité du réseau.}\\
\vspace{0.5cm}
\uncover<2>{$\times$ Nombre de saut}\\
\uncover<2>{\hspace{0.8cm}$\hookrightarrow$ Comme pour le GPS, non représentatif de la réactivité}\\
\vspace{0.5cm}
\uncover<3->{$\surd$ Temps de transfert}
 \end{itemize}
\uncover<4->{Calculer la distance à un centre lors de la diffusion des messages de présence du salon par addition des pings de proche en proche}
\end{small}
		\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Créer et détecter les salons, détecter l'état des participants
		\begin{frame}
			\frametitle{Gestion des salons}
\begin{small}
 \begin{itemize}
      \item<1-> Détecter un salon\\
	      \uncover<1->{\hspace{0.2cm}$\hookrightarrow$ Diffusion régulière de messages de présence du salon}\\
      \item<2-> Rejoindre un salon\\
	      \uncover<2->{\hspace{0.2cm}$\hookrightarrow$ Diffusion d'un message de participation}\\
      \item<3-> Participation à un salon\\
	 \begin{itemize}
	      \item<3-> Détecter les participants présents et les nouveaux\\
		      \uncover<3>{\hspace{1cm}$\times$ Demande de la liste aux voisins}\\
\vspace{0.2cm}
		      \uncover<4->{\hspace{1cm}$\surd$ Réception successive des messages de participation}\\
\vspace{0.2cm}
	      \item Détecter la déconnexion d'un participant\\
		      \uncover<5->{\hspace{1cm}$\hookrightarrow$ Timeout}\\
	 \end{itemize}
 \end{itemize}
\end{small}
		\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Quitter un salon
		\begin{frame}
			\frametitle{Gestion des salons}
\begin{small}
Quitter le salon\\
 \begin{itemize}
      \item<1-> Volontairement\\
	      \uncover<1->{\hspace{0.2cm}$\hookrightarrow$ Aucun message $\to$ utilisation d'un timeout pour les autres}\\
      \item<2-> Involontairement (éloignement, déconnexion)\\
	      \uncover<2->{\hspace{0.2cm}$\hookrightarrow$ Doit se rapprocher ou créer un nouveau salon $\to$ timeout pour les autres}\\
      \item<3-> Fermeture du salon\\
	 \begin{itemize}
	      \item<3-> Le centre ferme volontairement le salon\\
		      \uncover<3->{\hspace{1cm}$\hookrightarrow$ Le supléant prend le relais}\\
	      \item<4-> Le centre est trop loin\\
		      \uncover<4->{\hspace{1cm}$\hookrightarrow$ Doivent se rapprocher ou créer un nouveau salon, sinon déconnexion automatique après timeout}\\
	 \end{itemize}
 \end{itemize}
\end{small}
		\end{frame}

\subsection{Récapitulatif}
\begin{frame}
			\frametitle{Récapitulatif}
			\begin{itemize}
		      \item Utilisation de pings réguliers pour connaitre ses voisins\\
		      \item Utilisation de pings de salons retransmis pour connaitre les salons et leur centre\\
			     \item Gestion de la deconnexion du centre et des noeuds participants
			\end{itemize}
\end{frame}

\section{Développement}
	\subsection{Fonctionnement général}
		\begin{frame}
			\frametitle{Schéma de fonctionnement général}
				\begin{center}
					%\includegraphics[width=10cm,clip]{images/Schema_general.eps}
						\includegraphics[width=10cm,clip]{images/Schema_general.png}
				\end{center}
		\end{frame}

		\begin{frame}
			\frametitle{Structures de données}
		
				\begin{block}{}<1-6>
					\begin{tiny}
				      \textbf{listeSalons}(\#salonId,nom,connecte,*listeConnecte,idCentre,dernierContact,distance,estampille,*messageManquants)\\
				      \textbf{listeConnectes}(\#salonId, \#noeudId)\\
				      \textbf{messageManquants}(\#salonId, \#noeudId, \#numAction, nbdemandes)\\
					\end{tiny}
				\end{block}


				\begin{block}{}<2-6>
					\begin{tiny}
					 \textbf{historique}(\#salonId, \#noeudId, dernierNumAction, *listeMessages)\\
				      \textbf{messagesHisto}(\#salonId, \#noeudId, \#numAction, message, estampille)\\
					\end{tiny}
				\end{block}

				\begin{block}{}<3-6>
					\begin{tiny}
				     \textbf{listeMessages}(\#salonId, \#noeudId, message, estampille)\\
					\end{tiny}
				\end{block}


				\begin{block}{}<4-6>
					\begin{tiny}
				     \textbf{listeNoeuds}(\#noeudId, pseudo)\\
					\end{tiny}
				\end{block}


				\begin{block}{}<5-6>
					\begin{tiny}
				     \textbf{listeVoisins}(\#noeudId, distance, dernierContact)\\
					\end{tiny}
				\end{block}


				\begin{block}{}<6>
					\begin{tiny}
				     \textbf{horloge}(\#salonId, \#noeudId, numAction)\\
					\end{tiny}
				\end{block}

		\end{frame}

	\subsection{Réception d'un message}
		\begin{frame}
			\frametitle{Procèdure de réception d'un message}
				\begin{center}
					\includegraphics[height=6cm,clip,bb=0 0 1309 824]{images/devt_algo.png}
				\end{center}
		\end{frame}

	\subsection{Propagation des messages}
		\begin{frame}
			\frametitle{Procèdure de retransmission d'un message}
				\begin{center}
					\includegraphics[width=10cm,clip]{images/devt_retransmission.png}
			\end{center}
				\begin{block}{Message à destination des participants du salon}
					\begin{scriptsize}
					   	\uncover<2-3>{$\hookrightarrow$ Liste des participants n'ayant pas encore reçu le message.}\\
					   	\uncover<3>{$\hookrightarrow$ Liste des noeuds ayant relayé le message.}\\
						\uncover<4>{\hspace{0.2cm}$\hookrightarrow$ S'arrête quand la première liste est vide ou quand la limite de distance est dépassée.}\\
					\end{scriptsize}
				
				\end{block}
				
		\end{frame}

	\subsection{Messages manquants}
		\begin{frame}
			\frametitle{Demande de messages manquants}
				\begin{center}
					\includegraphics[height=6cm,clip]{images/devt_algoMessagesManquants2.png}
				
				\end{center}
		\end{frame}

		\begin{frame}
			\frametitle{Réception d'une demande de messages manquants}
				\begin{center}
					\includegraphics[width=10cm,clip]{images/devt_algoMessagesManquants3.png}
				\end{center}
		\end{frame}

	\begin{frame}
			\frametitle{Réception de messages manquants}
				\begin{center}
					\includegraphics[width=8cm,clip]{images/devt_algoMessagesManquants1.png}
				\end{center}
		\end{frame}

	\subsection{Chronologie des messages}
		\begin{frame}
			\frametitle{Réordonnancement des messages reçus}

				\begin{block}{Solutions}
					   	\uncover<1>{$\times$ Ordonnancement par noeud.}\\
					   	\uncover<1>{\hspace{0.2cm}$\hookrightarrow$ Horloges vectorielles suffisantes.}\\
						\vspace{0.6cm}
					   	\uncover<2>{$\surd$ Ordonnancement pour tous les noeuds.}\\
						\uncover<2>{\hspace{0.2cm}$\hookrightarrow$ Estampilles.}\\
				\end{block}



		\end{frame}

	


\subsection{Election de centre}
		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Algorithme d'élection
		\begin{frame}
			\frametitle{}
\begin{small}
Algorithmes d'élection de centre
 \begin{itemize}
      \item<1-5>{$\times$ Election à la déconnexion}\\
	      \uncover<2-5>{\hspace{0.2cm}$\surd$ Optimisation du choix du centre}\\
	      \uncover<3-5>{\hspace{0.2cm}$\times$ Utilisation de vagues dans un réseau fortement dynamique}\\
	      \uncover<4-5>{\hspace{0.2cm}$\times$ Latence ralentissant le service}\\
	      \uncover<4-5>{\hspace{0.8cm}$\hookrightarrow$ Certains noeuds peuvent se déconnecter}\\
	      \uncover<5>{\hspace{0.2cm}$\times$ Saturation du réseau}\\
	      \uncover<5>{\hspace{0.2cm}$\times$ Complexité de la fusion de salon}\\
\vspace{0.5cm}
      \item<6->{$\surd$ Election avant la déconnexion}\\
	      \uncover<7->{\hspace{0.2cm}$\thicksim$ Utilisation du noeud le plus proche comme centre suppléant}\\
	      \uncover<8->{\hspace{0.2cm}$\surd$ Algorithme simple et pas de message supplémentaire}\\
	      \uncover<9->{\hspace{0.2cm}$\surd$ Décision du nouveau centre imédiate}\\
	      \uncover<10->{\hspace{0.2cm}$\surd$ Fusion transparente du salon}
 \end{itemize}
\end{small}
		\end{frame}

\section{Démonstration}
		\begin{frame}
\begin{center}
					\includegraphics[width=6cm]{images/mouche.png}
				\end{center}
		\end{frame}


\section{Conclusion}
		\begin{frame}
			\frametitle{}
			\begin{block}{Conclusion}
				 \begin{itemize}
					\item Algorithmique répartie, domaine vaste et complexe
					\item Le réseau fortement dynamique induit une complexité supérieure
					\item Projet intéressant au point de vue organisationnel et technique
				\end{itemize}				
				\end{block}	

		\end{frame}

\end{document}